#include <utility>
#include <vector>
class Solution {
public:
    int getmid(vector<int>& nums,int begin,int end)
    {
        int n = nums.size();
        vector<int> f(n);//选择不偷i
        vector<int> g(n);//选择偷i
        g[begin] = nums[begin];
        for(int i = begin;i<=end;i++)
        {
            g[i] = max(f[i-1]+nums[i],f[i-1]);
            f[i] = max(f[i-1],g[i-1]);
        }
        return max(f[end],g[end]);
    }
    int rob(vector<int>& nums) {
       return max(getmid(nums,2,nums.size()-2)+nums[0],getmid(nums,1,nums.size()-1));
    }
};